/*
题目链接 : https://leetcode.cn/problems/maximum-total-beauty-of-the-gardens/description/?envType=daily-question&envId=2025-03-08
*/

//题解代码 : 
 #define ll long long
class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        vector<int> a;
        int x = 0;
        for(auto& it : flowers){
            if(it>=target){
                ++x;//>=target已经是完善花园了
            }else{
                a.emplace_back(it);//存储不完善的
            }
        }
        ll ans = 1LL*x*full;

        sort(a.begin(),a.end());
        int n = a.size();
        vector<ll> presum(n+1);//前缀和
        for(int i=1;i<=n;++i) presum[i] = presum[i-1]+a[i-1];

        //将a[i......j]范围全部变成mid是否可行
        auto check = [&](int i,int j,ll rest,ll mid)->bool{
            ll sum = presum[j+1] - presum[i];
            return ((j-i+1)*mid - sum) <= rest;
        };

        //优先使大的变完善,留下更多给小的
        for(int i=n;i>=0;--i){
            ll rightsum = presum[n]-presum[i];
            ll rightcnt = n-i;
            if(rightcnt*target-rightsum>newFlowers) break;
            ll rest = newFlowers - (rightcnt*target-rightsum);
            ll l = 0, r = target-1;
            while(l<=r){
                ll mid = (l+r)/2;
                int j = lower_bound(a.begin(),a.end(),mid) - a.begin() - 1;
                j = min(j,i-1);
                if(check(0,j,rest,mid)) l = mid+1;
                else r = mid - 1;
            }
            ans = max(ans,(i>0)*r*partial+(rightcnt+x)*full);
        }
        return ans;
    }
};
